As well known to those skilled in the art, stereo matching is a method of reconstructing three-dimensional spatial information from a pair of two-dimensional images. As shown in FIG. 1, stereo matching is a method of detecting a left and a right side pixel corresponding to a specific location (X, Y, Z) in three-dimensional space from image lines of epipolar lines on a right and a left side image, respectively. The disparity d between a pair of the corresponding pixels is defined by the equation d=xr−x1.
The disparity conveys distance information, and the gecmetrical characteristic referred to as a “depth” can be calculated therefrom. Therefore, if the disparity is calculated from input images in real time, three-dimensional distance information and shape information in an observation space can be measured.
The basic concept of the stereo matching method is disclosed in a thesis by Dhond, et al. (Umesh R. Dhond and J. K. Aggarwal, Configuration from Stereo—a review, IEEE Transactions on Systems, Man, and Cybernetics, 19(6):553-572, November/December 1989); and the latest stereo matching algorithm is summarized well in a thesis by Szeliski (D. Scharstein and R. Szeliski. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. IJCV 47(1/2/3):7-42, April-June 2002).
The stereo matching method includes a technique based on a winner-take-all process using a local cost; and a technique for establishing a global energy model and performing energy minimization on the basis thereof. By using the winner-take-all process, the stereo matching can be performed in a single scan line and the processing speed can be enhanced, but has a very large disparity error. The global energy model technique typically includes a graph cut technique, a belief propagation technique, etc. Both the graph cut technique and the belief propagation technique are based on energy minimization and exhibit excellent results, but require very long processing times. That is, the belief propagation technique exhibits excellent stereo matching results having small error by using the relation between upper and lower lines. In the belief propagation technique, messages are received from an adjacent processor during each sequence to be computed, and the computed messages are sent to an adjacent processor. Therefore, if the belief propagation technique is implemented as a hardware device to perform a high-speed parallel processing, the processing time can be shortened. Further, the belief propagation technique is configured such that messages are transferred from a current pixel position to an adjacent pixel position in a forward, a backward, an upward, and a downward direction, respectively.
However, although the above-described conventional real-time algorithms can perform a high-speed processing, they have large disparity matching errors. Further, since the conventional belief propagation technique is a sequential software algorithm, it has a small disparity matching error, but requires a long processing time.